package model.algorithm;

import java.util.ArrayList;
import java.util.HashMap;

public class AStar extends CommonHeuristicSearcher {
	private Heurictics h;
	
	public AStar(Heurictics h) {
		super();
		this.h = h;
	}

	@Override	// main use in the search function
	public ArrayList<Action> search(SearchDomain sd) {
		HashMap<State, Double> gCostMap = new HashMap<State, Double>();											// Will hold the g cost for each state-node (the known distance from start to here)
		ArrayList<State> openSet = new ArrayList<State>();							// OpenSet ArrayList - will help finding if a state is in the openList queue
		ArrayList<State> closedSet = new ArrayList<State>();						// ClosedSet ArrayList - The same for closedList queue
		
		State tmp = sd.getStartState();												// tmp = startState
		gCostMap.put(tmp, (double) 0);												// sets the GCost of the startState to 0
		tmp.setCost(h.getEvaluation(tmp, sd.getGoalState())+gCostMap.get(tmp));		// sets the FCost of the startState (h+g) 
		
		openSet.add(tmp);
		this.openList.add(tmp);														// initialize the openList with the startState 		
		
		while (!openList.isEmpty()){												// while the openList(&Set) aren't empty
			State currentState = openList.poll();									// pull out the first state from the openList queue and call it currentState
			openSet.remove(currentState);											// remove it from the openSet as well
		
			if (currentState.equals(sd.getGoalState()))									// if the current state is the goal state, we are actually finished
				return generatePath(currentState);									// so return the path through the generatePath method
		
			closedSet.add(currentState);											// add the state to the closed set
			closedList.add(currentState);											// and to the closedList queue
			
			HashMap<Action, State> successors = sd.getAllPossibleMoves(currentState);		//create a map of all the possible states we can go to
			for (Action act : successors.keySet()){											// run through all those states
				State son = successors.get(act);
				gCostMap.put(son, son.getCost() + act.getCost());							// set the son's new gCost
				if (closedSet.contains(son))												// if its already been dealt, go to the next one
					continue;
				double tmpGCost = gCostMap.get(currentState) + act.getCost();				// generate the tentative gCost of the currentState if we'll go to that son
				
				
				if ((!openSet.contains(son)) || ( tmpGCost < gCostMap.get(son))){			//if the son is'nt in the openList or that the tentative gCost is smaller than the gCost of the son
					son.setCameFrom(currentState);											//update the son's data members
					son.setPrevAct(act);														
					gCostMap.replace(son, tmpGCost);
					son.setCost(gCostMap.get(son) + h.getEvaluation(son, sd.getGoalState()));	// set the F cost of the son
					
					if (!openSet.contains(son)){												// if that son is'nt in to openList - add it!
						openSet.add(son);
						openList.add(son);
					}
				}
			}
		}
		return null;
	}

	private ArrayList<Action> generatePath(State state) {									//	private method that returns an arraylist of the rigth path.
	ArrayList<Action> actions = new ArrayList<Action>();									// it will mainly use the previous action data member of State
	do
	{
		actions.add(0, state.prevAct);
		state = state.cameFrom;
	} while (state.cameFrom != null);
	return actions;
	}
	
	@Override
	public String toString() {
		return "AStar";
	}
}